#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个整数数组 nums 和一个整数 k 。

找到 nums 中满足以下要求的最长子序列：

子序列 严格递增
子序列中相邻元素的差值 不超过 k 。
请你返回满足上述要求的 最长子序列 的长度。

子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。
 * */
int lengthOfLIS(vector<int>& nums, int k) {

    if (nums.size() <= 1) return nums.size();
    vector<int> dp(nums.size(), 1);
    int result = 0;
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]&&nums[i] -nums[j]<=k) dp[i] = max(dp[i], dp[j] + 1);
        }
        if (dp[i] > result) result = dp[i]; // 取⻓的⼦序列
    }
    return result;

}